package com.zhugang.week10;

/**
 * @program algorithms
 * @description: rob
 * @author: chanzhugang
 * @create: 2022/08/30 15:25
 */
public class Rob {

    /**
     * 198 打家劫舍
     *
     * @param nums
     * @return
     */
    public int rob(int[] nums) {
        // 相邻的房屋不能同一次偷取，求偷取金额最大值
        // int dp[n][2] ：记录每个阶段的状态
        // dp[i][0] ： 第i个物品不偷时，当下的最大金额
        // dp[i][1] ： 第i个物品偷时，当下的最大金额

        int n = nums.length;
        // 定义状态
        int[][] dp = new int[n][2];
        // 第一家没偷
        dp[0][0] = 0;
        // 第一家偷了
        dp[0][1] = nums[0];

        for (int i = 1; i < n; i++) {
            // i没偷， 所以i-1可以偷也可以不偷
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);
            // i偷了，所以i-1只能没偷
            dp[i][1] = dp[i - 1][0] + nums[i];
        }
        // n - 1 时偷或者没偷取最大值
        return Math.max(dp[n - 1][0], dp[n - 1][1]);
    }
}